<!doctype html>
<html class="theme-next use-motion theme-next-mist">
<head>
  

<meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>


<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />








  <link rel="stylesheet" type="text/css" href="/vendors/fancybox/source/jquery.fancybox.css?v=2.1.5"/>




<link rel="stylesheet" type="text/css" href="/css/main.css?v=0.4.5.1"/>




  <meta name="keywords" content="数据结构," />



  <link rel="alternate" href="/atom.xml" title="laphets's Blog" type="application/atom+xml" />



  <link rel="shorticon icon" type="image/x-icon" href="/favicon.ico?v=0.4.5.1" />


<meta name="description" content="线段树的定义线段树(segment tree)是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。
线段树的作用

有一列数，初始值全为0，每次可以进行以下三种操作中的一种：(1)给指定区间每个数加上一个">
<meta property="og:type" content="article">
<meta property="og:title" content="浅谈线段树及其应用">
<meta property="og:url" content="http://laphets.com/2015/10/22/浅谈线段树及其应用/index.html">
<meta property="og:site_name" content="laphets's Blog">
<meta property="og:description" content="线段树的定义线段树(segment tree)是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。
线段树的作用

有一列数，初始值全为0，每次可以进行以下三种操作中的一种：(1)给指定区间每个数加上一个">
<meta property="og:updated_time" content="2015-10-23T09:22:34.000Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="浅谈线段树及其应用">
<meta name="twitter:description" content="线段树的定义线段树(segment tree)是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。
线段树的作用

有一列数，初始值全为0，每次可以进行以下三种操作中的一种：(1)给指定区间每个数加上一个">


<script type="text/javascript" id="hexo.configuration">
  var CONFIG = {
    scheme: 'Mist',
    sidebar: 'post'
  };
</script>



  <title> 浅谈线段树及其应用 | laphets's Blog </title>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  <!--[if lte IE 8]>
  <div style=' clear: both; height: 59px; padding:0 0 0 15px; position: relative;margin:0 auto;'>
    <a href="http://windows.microsoft.com/en-US/internet-explorer/products/ie/home?ocid=ie6_countdown_bannercode">
      <img src="http://7u2nvr.com1.z0.glb.clouddn.com/picouterie.jpg" border="0" height="42" width="820"
           alt="You are using an outdated browser. For a faster, safer browsing experience, upgrade for free today or use other browser ,like chrome firefox safari."
           style='margin-left:auto;margin-right:auto;display: block;'/>
    </a>
  </div>
<![endif]-->
  






  <div class="container one-column page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><h1 class="site-meta">
  <span class="logo-line-before"><i></i></span>
  <a href="/" class="brand" rel="start">
      <span class="logo">
        <i class="icon-next-logo"></i>
      </span>
      <span class="site-title">laphets's Blog</span>
  </a>
  <span class="logo-line-after"><i></i></span>
</h1>

<div class="site-nav-toggle">
  <button>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
  </button>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu ">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            <i class="menu-item-icon icon-next-home"></i> <br />
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories" rel="section">
            <i class="menu-item-icon icon-next-categories"></i> <br />
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags" rel="section">
            <i class="menu-item-icon icon-next-tags"></i> <br />
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about" rel="section">
            <i class="menu-item-icon icon-next-about"></i> <br />
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives" rel="section">
            <i class="menu-item-icon icon-next-archives"></i> <br />
            归档
          </a>
        </li>
      

      
      
    </ul>
  

  
</nav>

 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div id="content" class="content"> 

  <div id="posts" class="posts-expand">
    

  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
    <header class="post-header">

      
      
        <h1 class="post-title" itemprop="name headline">
          
          
            
              浅谈线段树及其应用
            
          
        </h1>
      

      <div class="post-meta">
        <span class="post-time">
          发表于
          <time itemprop="dateCreated" datetime="2015-10-22T21:07:15+08:00" content="2015-10-22">
            2015-10-22
          </time>
        </span>

        
          <span class="post-category" >
            &nbsp; | &nbsp; 分类于
            
              <span itemprop="about" itemscope itemtype="https://schema.org/Thing">
                <a href="/categories/理性/" itemprop="url" rel="index">
                  <span itemprop="name">理性</span>
                </a>
              </span>

              
              

            
          </span>
        

        
          
            <span class="post-comments-count">
              &nbsp; | &nbsp;
              <a href="/2015/10/22/浅谈线段树及其应用/#comments" itemprop="discussionUrl">
                <span class="post-comments-count ds-thread-count" data-thread-key="2015/10/22/浅谈线段树及其应用/" itemprop="commentsCount"></span>
              </a>
            </span>
          
        
        
      </div>
    </header>

    <div class="post-body">

      
      

      
        <span itemprop="articleBody"><h2 id="线段树的定义">线段树的定义</h2><p>线段树(<em>segment tree</em>)是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。<br>使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。</p>
<h2 id="线段树的作用">线段树的作用</h2><blockquote>
<blockquote>
<p>有一列数，初始值全为0，每次可以进行以下三种操作中的一种：<br>(1)给指定区间每个数加上一个值<br>(2)将指定区间所有数置成一个统一的值<br>(3)询问一个区间上的最小值、最大值、所有数的和</p>
</blockquote>
</blockquote>
<h2 id="线段树的存储">线段树的存储</h2><figure class="highlight swift"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Node</span></span><br><span class="line"></span>&#123;</span><br><span class="line">	int <span class="keyword">left</span>,<span class="keyword">right</span>;</span><br><span class="line">	int <span class="built_in">min</span>,<span class="built_in">max</span>,sum;</span><br><span class="line">	<span class="type">Node</span> *leftchild,*rightchild;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="线段树的构造">线段树的构造</h2><figure class="highlight zephir"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">void build(Node *cur,<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span><br><span class="line">&#123;</span><br><span class="line">	cur-&gt;left=l;</span><br><span class="line">	cur-&gt;right=r;</span><br><span class="line">	<span class="keyword">if</span>(l!=r)</span><br><span class="line">	&#123;</span><br><span class="line">		cur-&gt;leftchild=<span class="keyword">new</span> Node;</span><br><span class="line">		cur-&gt;rightchild=<span class="keyword">new</span> Node;</span><br><span class="line">		build(cur-&gt;leftchild,l,(l+r)/<span class="number">2</span>);</span><br><span class="line">		build(cur-&gt;rightchild,(l+r)/<span class="number">2</span>+<span class="number">1</span>,r);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">		cur-&gt;leftchild=cur-&gt;rightchild=<span class="keyword">NULL</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="在线段树上对元素进行修改">在线段树上对元素进行修改</h2><p>将线段树上位置为x的元素修改成num<br><figure class="highlight lasso"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="literal">void</span> insert(Node *cur,int x,int num)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>left==cur<span class="subst">-&gt;</span>right)</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">min</span>=cur<span class="subst">-&gt;</span><span class="keyword">max</span>=cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=num;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(x&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			insert(lc,x,num);</span><br><span class="line">		<span class="keyword">if</span>(x&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			insert(rc,x,num);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=lc<span class="subst">-&gt;</span><span class="keyword">sum</span>+rc<span class="subst">-&gt;</span><span class="keyword">sum</span>;</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">max</span>=<span class="keyword">max</span>(lc<span class="subst">-&gt;</span><span class="keyword">max</span>,rc<span class="subst">-&gt;</span><span class="keyword">max</span>);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">min</span>=<span class="keyword">min</span>(lc<span class="subst">-&gt;</span><span class="keyword">min</span>,rc<span class="subst">-&gt;</span><span class="keyword">min</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="对线段树的某一个区间进行询问">对线段树的某一个区间进行询问</h2><p>询问区间[l,r]所有元素和<br><figure class="highlight rust"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> querysum(Node *cur,<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur-&gt;leftchild,*rc=cur-&gt;rightchild;</span><br><span class="line">	<span class="keyword">int</span> ret=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">if</span>((l&lt;=cur-&gt;left)&amp;&amp;(cur-&gt;right&lt;=r))</span><br><span class="line">		ret+=cur-&gt;sum;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(l&lt;=(cur-&gt;left+cur-&gt;right)/<span class="number">2</span>)</span><br><span class="line">			ret+=querysum(lc,l,r);</span><br><span class="line">		<span class="keyword">if</span>(r&gt;(cur-&gt;left+cur-&gt;right)/<span class="number">2</span>)</span><br><span class="line">			ret+=querysum(rc,l,r);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ret;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="那么对于整个区间进行操作呢？">那么对于整个区间进行操作呢？</h2><p>是不是需要对每一个元素都进行insert()操作呢？<br>显然不行，那样的话每一次操作都要$O(nlogn)$，失去了线段树的优势。</p>
<h3 id="lazy-tag技术："><strong>lazy-tag</strong>技术：</h3><blockquote>
<blockquote>
<p>lazy-tag的思想就是在对区间进行更新的时候，在分解出来的区间上打上作用于整个子树的标记<br>当在对这个区间进行维护或者查询的时候便将这个标记进行分解，并将其传递到它的两个子树上。</p>
</blockquote>
</blockquote>
<h2 id="对一个区间整体加上一个数">对一个区间整体加上一个数</h2><p>将区间[l,r]整体加上delta<br><figure class="highlight lasso"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="literal">void</span> update(Node *cur,int l,int r,int delta)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	<span class="keyword">if</span>((l&lt;=cur<span class="subst">-&gt;</span>left)<span class="subst">&amp;&amp;</span>(cur<span class="subst">-&gt;</span>right&lt;=r))</span><br><span class="line">		cur<span class="subst">-&gt;</span>delta+=delta;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(l&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			update(lc,l,r,delta);</span><br><span class="line">		<span class="keyword">if</span>(r&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			update(rc,l,r,delta);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=lc<span class="subst">-&gt;</span><span class="keyword">sum</span>+lc<span class="subst">-&gt;</span>delta*(lc<span class="subst">-&gt;</span>right<span class="attribute">-lc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>+=rc<span class="subst">-&gt;</span><span class="keyword">sum</span>+rc<span class="subst">-&gt;</span>delta*(rc<span class="subst">-&gt;</span>right<span class="attribute">-rc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="使用lazy-tag技术对元素进行修改">使用<strong>lazy-tag</strong>技术对元素进行修改</h2><p>将位置为x的元素修改为num<br><figure class="highlight lasso"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="literal">void</span> insert(Node *cur,int x,int num)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>left==cur<span class="subst">-&gt;</span>right)</span><br><span class="line">	&#123;</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=num;</span><br><span class="line">		cur<span class="subst">-&gt;</span>delta=<span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		lc<span class="subst">-&gt;</span>delta+=cur<span class="subst">-&gt;</span>delta;</span><br><span class="line">		rc<span class="subst">-&gt;</span>delta+=cur<span class="subst">-&gt;</span>delta;</span><br><span class="line">		cur<span class="subst">-&gt;</span>delta=<span class="number">0</span>;</span><br><span class="line">		<span class="keyword">if</span>(x&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			insert(lc,x,num);</span><br><span class="line">		<span class="keyword">if</span>(x&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			insert(rc,x,num);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=lc<span class="subst">-&gt;</span><span class="keyword">sum</span>+lc<span class="subst">-&gt;</span>delta*(lc<span class="subst">-&gt;</span>right<span class="attribute">-lc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>+=rc<span class="subst">-&gt;</span><span class="keyword">sum</span>+rc<span class="subst">-&gt;</span>delta*(rc<span class="subst">-&gt;</span>right<span class="attribute">-rc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="使用lazy-tag技术对区间进行查询">使用<strong>lazy-tag</strong>技术对区间进行查询</h2><p>询问区间[l,r]上所有元素的和<br><figure class="highlight lasso"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line">int querysum(Node *cur,int l,int r)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	int ret=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">if</span>((l&lt;=cur<span class="subst">-&gt;</span>left)<span class="subst">&amp;&amp;</span>(cur<span class="subst">-&gt;</span>right&lt;=r))</span><br><span class="line">		ret+=cur<span class="subst">-&gt;</span><span class="keyword">sum</span>+(cur<span class="subst">-&gt;</span>right<span class="attribute">-cur</span><span class="subst">-&gt;</span>left+<span class="number">1</span>)*cur<span class="subst">-&gt;</span>delta;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		lc<span class="subst">-&gt;</span>delta+=cur<span class="subst">-&gt;</span>delta;</span><br><span class="line">		rc<span class="subst">-&gt;</span>delta+=cur<span class="subst">-&gt;</span>delta;</span><br><span class="line">		cur<span class="subst">-&gt;</span>delta=<span class="number">0</span>;</span><br><span class="line">		<span class="keyword">if</span>(l&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			ret+=querysum(lc,l,r);</span><br><span class="line">		<span class="keyword">if</span>(r&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			ret+=querysum(rc,l,r);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=lc<span class="subst">-&gt;</span><span class="keyword">sum</span>+lc<span class="subst">-&gt;</span>delta*(lc<span class="subst">-&gt;</span>right<span class="attribute">-lc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>+=rc<span class="subst">-&gt;</span><span class="keyword">sum</span>+rc<span class="subst">-&gt;</span>delta*(rc<span class="subst">-&gt;</span>right<span class="attribute">-rc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ret;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="将一个区间整体置为一个数">将一个区间整体置为一个数</h2><p>额外维护两个域en表示一个区间是否为统一的数，若en有效，则data域表示区间统一的数的数值。<br>同样，我们可以用<strong>lazy-tag</strong>来维护这种操作</p>
<h2 id="求一个节点表示区间上所有元素的和">求一个节点表示区间上所有元素的和</h2><figure class="highlight lasso"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">inline</span> int clacsum(Node *cur)</span><br><span class="line">&#123;</span><br><span class="line">	<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>en)</span><br><span class="line">		<span class="keyword">return</span> (cur<span class="subst">-&gt;</span>right<span class="attribute">-cur</span><span class="subst">-&gt;</span>left+<span class="number">1</span>)*cur<span class="subst">-&gt;</span><span class="built_in">data</span>;</span><br><span class="line">	<span class="keyword">return</span> cur<span class="subst">-&gt;</span><span class="keyword">sum</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="修改一个节点的值">修改一个节点的值</h2><p>将位置为x的元素修改为num<br><figure class="highlight lasso"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="literal">void</span> insert(Node *cur,int x,int num)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>left==cur<span class="subst">-&gt;</span>right)</span><br><span class="line">	&#123;</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=num;</span><br><span class="line">		cur<span class="subst">-&gt;</span>en=<span class="literal">false</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>en)</span><br><span class="line">		&#123;</span><br><span class="line">			lc<span class="subst">-&gt;</span><span class="built_in">data</span>=rc<span class="subst">-&gt;</span><span class="built_in">data</span>=cur<span class="subst">-&gt;</span><span class="built_in">data</span>;</span><br><span class="line">			lc<span class="subst">-&gt;</span>en=rc<span class="subst">-&gt;</span>en=<span class="literal">true</span>;</span><br><span class="line">			cur<span class="subst">-&gt;</span>en=<span class="literal">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(x&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			insert(lc,x,num);</span><br><span class="line">		<span class="keyword">if</span>(x&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			insert(rc,x,num);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=clacsum(lc)+clacsum(rc);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="修改整个区间的值">修改整个区间的值</h2><p>将区间[l,r]上所有元素的值置为num<br><figure class="highlight lasso"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="literal">void</span> update(Node *cur,int l,int r,int num)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>en)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(lc!=<span class="built_in">NULL</span>)</span><br><span class="line">		&#123;</span><br><span class="line">			lc<span class="subst">-&gt;</span><span class="built_in">data</span>=num;</span><br><span class="line">			lc<span class="subst">-&gt;</span>en=<span class="literal">true</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(rc!=<span class="built_in">NULL</span>)</span><br><span class="line">		&#123;</span><br><span class="line">			rc<span class="subst">-&gt;</span><span class="built_in">data</span>=num;</span><br><span class="line">			rc<span class="subst">-&gt;</span>en=<span class="literal">true</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>((l&lt;=cur<span class="subst">-&gt;</span>left)<span class="subst">&amp;&amp;</span>(cur<span class="subst">-&gt;</span>right&lt;=r))</span><br><span class="line">	&#123;</span><br><span class="line">		cur<span class="subst">-&gt;</span>en=<span class="literal">true</span>;</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="built_in">data</span>=num;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(l&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			update(lc,l,r,num);</span><br><span class="line">		<span class="keyword">if</span>(r&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right))</span><br><span class="line">			update(rc,l,r,num);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=calcsum(lc)+calcsum(rc);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="查询区间的和">查询区间的和</h2><p>询问区间[l,r]上所有元素的和<br><figure class="highlight lasso"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">int querysum(Node *cur,int l,int r)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	int ret=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">if</span>((l&lt;=cur<span class="subst">-&gt;</span>left)<span class="subst">&amp;&amp;</span>(cur<span class="subst">-&gt;</span>right&lt;=r))<span class="subst">\</span></span><br><span class="line">		ret+=clacsum(cur);</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>en)</span><br><span class="line">		&#123;</span><br><span class="line">			lc<span class="subst">-&gt;</span><span class="built_in">data</span>=cur<span class="subst">-&gt;</span><span class="built_in">data</span>;</span><br><span class="line">			lc<span class="subst">-&gt;</span>en=<span class="literal">true</span>;</span><br><span class="line">			rc<span class="subst">-&gt;</span><span class="built_in">data</span>=cur<span class="subst">-&gt;</span><span class="built_in">data</span>;</span><br><span class="line">			rc<span class="subst">-&gt;</span>en=<span class="literal">true</span>;</span><br><span class="line">			cur<span class="subst">-&gt;</span>en=<span class="literal">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(l&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			ret+=querysum(lc,l,r);</span><br><span class="line">		<span class="keyword">if</span>(r&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			ret+=querysum(rc,l,r);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=lc<span class="subst">-&gt;</span><span class="keyword">sum</span>+lc<span class="subst">-&gt;</span>delta*(lc<span class="subst">-&gt;</span>right<span class="attribute">-lc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>+=rc<span class="subst">-&gt;</span><span class="keyword">sum</span>+rc<span class="subst">-&gt;</span>delta*(rc<span class="subst">-&gt;</span>right<span class="attribute">-rc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ret;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="总结">总结</h2><p><strong>到这里就差不多写完了，把所有操作的代码汇个总:</strong><br><figure class="highlight lasso"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br></pre></td><td class="code"><pre><span class="line"><span class="variable">#include</span>&lt;iostream&gt;</span><br><span class="line"><span class="variable">#include</span>&lt;cstdio&gt;</span><br><span class="line"><span class="variable">#include</span>&lt;algorithm&gt;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">struct Node</span><br><span class="line">&#123;</span><br><span class="line">	int left,right;</span><br><span class="line">	int <span class="keyword">min</span>,<span class="keyword">max</span>,<span class="keyword">sum</span>,delta;</span><br><span class="line">	bool en;</span><br><span class="line">	Node *leftchild,*rightchild;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="literal">void</span> build(Node *cur,int l,int r)</span><br><span class="line">&#123;</span><br><span class="line">	cur<span class="subst">-&gt;</span>left=l;</span><br><span class="line">	cur<span class="subst">-&gt;</span>right=r;</span><br><span class="line">	<span class="keyword">if</span>(l!=r)</span><br><span class="line">	&#123;</span><br><span class="line">		cur<span class="subst">-&gt;</span>leftchild=<span class="literal">new</span> Node;</span><br><span class="line">		cur<span class="subst">-&gt;</span>rightchild=<span class="literal">new</span> Node;</span><br><span class="line">		build(cur<span class="subst">-&gt;</span>leftchild,l,(l+r)/<span class="number">2</span>);</span><br><span class="line">		build(cur<span class="subst">-&gt;</span>rightchild,(l+r)/<span class="number">2</span>+<span class="number">1</span>,r);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">		cur<span class="subst">-&gt;</span>leftchild=cur<span class="subst">-&gt;</span>rightchild=<span class="built_in">NULL</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="literal">void</span> insert(Node *cur,int x,int num)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>left==cur<span class="subst">-&gt;</span>right)</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">min</span>=cur<span class="subst">-&gt;</span><span class="keyword">max</span>=cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=num;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(x&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			insert(lc,x,num);</span><br><span class="line">		<span class="keyword">if</span>(x&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			insert(rc,x,num);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=lc<span class="subst">-&gt;</span><span class="keyword">sum</span>+rc<span class="subst">-&gt;</span><span class="keyword">sum</span>;</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">max</span>=<span class="keyword">max</span>(lc<span class="subst">-&gt;</span><span class="keyword">max</span>,rc<span class="subst">-&gt;</span><span class="keyword">max</span>);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">min</span>=<span class="keyword">min</span>(lc<span class="subst">-&gt;</span><span class="keyword">min</span>,rc<span class="subst">-&gt;</span><span class="keyword">min</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int querysum(Node *cur,int l,int r)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	int ret=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">if</span>((l&lt;=cur<span class="subst">-&gt;</span>left)<span class="subst">&amp;&amp;</span>(cur<span class="subst">-&gt;</span>right&lt;=r))</span><br><span class="line">		ret+=cur<span class="subst">-&gt;</span><span class="keyword">sum</span>;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(l&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			ret+=querysum(lc,l,r);</span><br><span class="line">		<span class="keyword">if</span>(r&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			ret+=querysum(rc,l,r);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ret;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//range</span></span><br><span class="line"><span class="literal">void</span> update(Node *cur,int l,int r,int delta)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	<span class="keyword">if</span>((l&lt;=cur<span class="subst">-&gt;</span>left)<span class="subst">&amp;&amp;</span>(cur<span class="subst">-&gt;</span>right&lt;=r))</span><br><span class="line">		cur<span class="subst">-&gt;</span>delta+=delta;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(l&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			update(lc,l,r,delta);</span><br><span class="line">		<span class="keyword">if</span>(r&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			update(rc,l,r,delta);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=lc<span class="subst">-&gt;</span><span class="keyword">sum</span>+lc<span class="subst">-&gt;</span>delta*(lc<span class="subst">-&gt;</span>right<span class="attribute">-lc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>+=rc<span class="subst">-&gt;</span><span class="keyword">sum</span>+rc<span class="subst">-&gt;</span>delta*(rc<span class="subst">-&gt;</span>right<span class="attribute">-rc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="literal">void</span> insert(Node *cur,int x,int num)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>left==cur<span class="subst">-&gt;</span>right)</span><br><span class="line">	&#123;</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=num;</span><br><span class="line">		cur<span class="subst">-&gt;</span>delta=<span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		lc<span class="subst">-&gt;</span>delta+=cur<span class="subst">-&gt;</span>delta;</span><br><span class="line">		rc<span class="subst">-&gt;</span>delta+=cur<span class="subst">-&gt;</span>delta;</span><br><span class="line">		cur<span class="subst">-&gt;</span>delta=<span class="number">0</span>;</span><br><span class="line">		<span class="keyword">if</span>(x&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			insert(lc,x,num);</span><br><span class="line">		<span class="keyword">if</span>(x&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			insert(rc,x,num);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=lc<span class="subst">-&gt;</span><span class="keyword">sum</span>+lc<span class="subst">-&gt;</span>delta*(lc<span class="subst">-&gt;</span>right<span class="attribute">-lc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>+=rc<span class="subst">-&gt;</span><span class="keyword">sum</span>+rc<span class="subst">-&gt;</span>delta*(rc<span class="subst">-&gt;</span>right<span class="attribute">-rc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int querysum(Node *cur,int l,int r)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	int ret=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">if</span>((l&lt;=cur<span class="subst">-&gt;</span>left)<span class="subst">&amp;&amp;</span>(cur<span class="subst">-&gt;</span>right&lt;=r))</span><br><span class="line">		ret+=cur<span class="subst">-&gt;</span><span class="keyword">sum</span>+(cur<span class="subst">-&gt;</span>right<span class="attribute">-cur</span><span class="subst">-&gt;</span>left+<span class="number">1</span>)*cur<span class="subst">-&gt;</span>delta;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		lc<span class="subst">-&gt;</span>delta+=cur<span class="subst">-&gt;</span>delta;</span><br><span class="line">		rc<span class="subst">-&gt;</span>delta+=cur<span class="subst">-&gt;</span>delta;</span><br><span class="line">		cur<span class="subst">-&gt;</span>delta=<span class="number">0</span>;</span><br><span class="line">		<span class="keyword">if</span>(l&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			ret+=querysum(lc,l,r);</span><br><span class="line">		<span class="keyword">if</span>(r&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			ret+=querysum(rc,l,r);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=lc<span class="subst">-&gt;</span><span class="keyword">sum</span>+lc<span class="subst">-&gt;</span>delta*(lc<span class="subst">-&gt;</span>right<span class="attribute">-lc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>+=rc<span class="subst">-&gt;</span><span class="keyword">sum</span>+rc<span class="subst">-&gt;</span>delta*(rc<span class="subst">-&gt;</span>right<span class="attribute">-rc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ret;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//all range</span></span><br><span class="line"><span class="keyword">inline</span> int clacsum(Node *cur)</span><br><span class="line">&#123;</span><br><span class="line">	<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>en)</span><br><span class="line">		<span class="keyword">return</span> (cur<span class="subst">-&gt;</span>right<span class="attribute">-cur</span><span class="subst">-&gt;</span>left+<span class="number">1</span>)*cur<span class="subst">-&gt;</span><span class="built_in">data</span>;</span><br><span class="line">	<span class="keyword">return</span> cur<span class="subst">-&gt;</span><span class="keyword">sum</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="literal">void</span> insert(Node *cur,int x,int num)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>left==cur<span class="subst">-&gt;</span>right)</span><br><span class="line">	&#123;</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=num;</span><br><span class="line">		cur<span class="subst">-&gt;</span>en=<span class="literal">false</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>en)</span><br><span class="line">		&#123;</span><br><span class="line">			lc<span class="subst">-&gt;</span><span class="built_in">data</span>=rc<span class="subst">-&gt;</span><span class="built_in">data</span>=cur<span class="subst">-&gt;</span><span class="built_in">data</span>;</span><br><span class="line">			lc<span class="subst">-&gt;</span>en=rc<span class="subst">-&gt;</span>en=<span class="literal">true</span>;</span><br><span class="line">			cur<span class="subst">-&gt;</span>en=<span class="literal">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(x&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			insert(lc,x,num);</span><br><span class="line">		<span class="keyword">if</span>(x&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			insert(rc,x,num);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=clacsum(lc)+clacsum(rc);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="literal">void</span> update(Node *cur,int l,int r,int num)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>en)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(lc!=<span class="built_in">NULL</span>)</span><br><span class="line">		&#123;</span><br><span class="line">			lc<span class="subst">-&gt;</span><span class="built_in">data</span>=num;</span><br><span class="line">			lc<span class="subst">-&gt;</span>en=<span class="literal">true</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(rc!=<span class="built_in">NULL</span>)</span><br><span class="line">		&#123;</span><br><span class="line">			rc<span class="subst">-&gt;</span><span class="built_in">data</span>=num;</span><br><span class="line">			rc<span class="subst">-&gt;</span>en=<span class="literal">true</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>((l&lt;=cur<span class="subst">-&gt;</span>left)<span class="subst">&amp;&amp;</span>(cur<span class="subst">-&gt;</span>right&lt;=r))</span><br><span class="line">	&#123;</span><br><span class="line">		cur<span class="subst">-&gt;</span>en=<span class="literal">true</span>;</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="built_in">data</span>=num;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(l&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			update(lc,l,r,num);</span><br><span class="line">		<span class="keyword">if</span>(r&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right))</span><br><span class="line">			update(rc,l,r,num);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=calcsum(lc)+calcsum(rc);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int querysum(Node *cur,int l,int r)</span><br><span class="line">&#123;</span><br><span class="line">	Node *lc=cur<span class="subst">-&gt;</span>leftchild,*rc=cur<span class="subst">-&gt;</span>rightchild;</span><br><span class="line">	int ret=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">if</span>((l&lt;=cur<span class="subst">-&gt;</span>left)<span class="subst">&amp;&amp;</span>(cur<span class="subst">-&gt;</span>right&lt;=r))<span class="subst">\</span></span><br><span class="line">		ret+=clacsum(cur);</span><br><span class="line">	<span class="keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(cur<span class="subst">-&gt;</span>en)</span><br><span class="line">		&#123;</span><br><span class="line">			lc<span class="subst">-&gt;</span><span class="built_in">data</span>=cur<span class="subst">-&gt;</span><span class="built_in">data</span>;</span><br><span class="line">			lc<span class="subst">-&gt;</span>en=<span class="literal">true</span>;</span><br><span class="line">			rc<span class="subst">-&gt;</span><span class="built_in">data</span>=cur<span class="subst">-&gt;</span><span class="built_in">data</span>;</span><br><span class="line">			rc<span class="subst">-&gt;</span>en=<span class="literal">true</span>;</span><br><span class="line">			cur<span class="subst">-&gt;</span>en=<span class="literal">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(l&lt;=(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			ret+=querysum(lc,l,r);</span><br><span class="line">		<span class="keyword">if</span>(r&gt;(cur<span class="subst">-&gt;</span>left+cur<span class="subst">-&gt;</span>right)/<span class="number">2</span>)</span><br><span class="line">			ret+=querysum(rc,l,r);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>=lc<span class="subst">-&gt;</span><span class="keyword">sum</span>+lc<span class="subst">-&gt;</span>delta*(lc<span class="subst">-&gt;</span>right<span class="attribute">-lc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">		cur<span class="subst">-&gt;</span><span class="keyword">sum</span>+=rc<span class="subst">-&gt;</span><span class="keyword">sum</span>+rc<span class="subst">-&gt;</span>delta*(rc<span class="subst">-&gt;</span>right<span class="attribute">-rc</span><span class="subst">-&gt;</span>left+<span class="number">1</span>);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> ret;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
</span>
      
    </div>

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/数据结构/" rel="tag">#数据结构</a>
          
        </div>
      

      
        <div class="post-nav">
          <div class="post-nav-prev post-nav-item">
            
              <a href="/2015/10/24/他/" rel="prev">他</a>
            
          </div>

          <div class="post-nav-next post-nav-item">
            
              <a href="/2015/10/19/浅谈ST算法在RMQ问题中的应用/" rel="next">浅谈ST算法在RMQ问题中的应用</a>
            
          </div>
        </div>
      

      
      
    </footer>
  </article>



    <div class="post-spread">
      
    </div>
  </div>

 </div>

        

        
          <div class="comments" id="comments">
            
              <div class="ds-thread" data-thread-key="2015/10/22/浅谈线段树及其应用/"
                   data-title="浅谈线段树及其应用" data-url="http://laphets.com/2015/10/22/浅谈线段树及其应用/">
              </div>
            
          </div>
        
      </div>

      
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" src="http://ww2.sinaimg.cn/small/005P1zB8gw1ex43mq0tx6j30bh0bijri.jpg" alt="laphets" itemprop="image"/>
          <p class="site-author-name" itemprop="name">laphets</p>
        </div>
        <p class="site-description motion-element" itemprop="description"></p>
        <nav class="site-state motion-element">
          <div class="site-state-item site-state-posts">
            <a href="/archives">
              <span class="site-state-item-count">17</span>
              <span class="site-state-item-name">日志</span>
            </a>
          </div>

          <div class="site-state-item site-state-categories">
            <a href="/categories">
              <span class="site-state-item-count">2</span>
              <span class="site-state-item-name">分类</span>
              </a>
          </div>

          <div class="site-state-item site-state-tags">
            <a href="/tags">
              <span class="site-state-item-count">8</span>
              <span class="site-state-item-name">标签</span>
              </a>
          </div>

        </nav>

        
          <div class="feed-link motion-element">
            <a href="/atom.xml" rel="alternate">
              <i class="menu-item-icon icon-next-feed"></i>
              RSS
            </a>
          </div>
        

        <div class="links-of-author motion-element">
          
            
              <span class="links-of-author-item">
                <a href="https://github.com/laphets" target="_blank">GitHub</a>
              </span>
            
              <span class="links-of-author-item">
                <a href="http://www.zhihu.com/people/luo-wen-qing-3-9" target="_blank">知乎</a>
              </span>
            
              <span class="links-of-author-item">
                <a href="http://wpa.qq.com/msgrd?v=3&uin=451295859&site=qq&menu=yes" target="_blank">QQ</a>
              </span>
            
          
        </div>

        
        

        <div class="links-of-author motion-element">
          
            <p class="site-author-name">Links</p>
            
              <span class="links-of-author-item">
              <a href="http://leafpigbirds.win" target="_blank">leafpigbirds</a>
              </span>
            
              <span class="links-of-author-item">
              <a href="http://www.cnblogs.com/vb4896" target="_blank">lzw</a>
              </span>
            
              <span class="links-of-author-item">
              <a href="http://www.cnblogs.com/lsdsjy" target="_blank">lsdsjy</a>
              </span>
            
              <span class="links-of-author-item">
              <a href="http://medalplus.com" target="_blank">medalplus</a>
              </span>
            
              <span class="links-of-author-item">
              <a href="http://orzer.me" target="_blank">Algorithm Works</a>
              </span>
            
          
        </div>

      </section>

      
        <section class="post-toc-wrap sidebar-panel-active">
          <div class="post-toc-indicator-top post-toc-indicator"></div>
          <div class="post-toc">
            
            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#线段树的定义"><span class="nav-number">1.</span> <span class="nav-text">线段树的定义</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#线段树的作用"><span class="nav-number">2.</span> <span class="nav-text">线段树的作用</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#线段树的存储"><span class="nav-number">3.</span> <span class="nav-text">线段树的存储</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#线段树的构造"><span class="nav-number">4.</span> <span class="nav-text">线段树的构造</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#在线段树上对元素进行修改"><span class="nav-number">5.</span> <span class="nav-text">在线段树上对元素进行修改</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#对线段树的某一个区间进行询问"><span class="nav-number">6.</span> <span class="nav-text">对线段树的某一个区间进行询问</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#那么对于整个区间进行操作呢？"><span class="nav-number">7.</span> <span class="nav-text">那么对于整个区间进行操作呢？</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#lazy-tag技术："><span class="nav-number">7.1.</span> <span class="nav-text">lazy-tag技术：</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#对一个区间整体加上一个数"><span class="nav-number">8.</span> <span class="nav-text">对一个区间整体加上一个数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#使用lazy-tag技术对元素进行修改"><span class="nav-number">9.</span> <span class="nav-text">使用lazy-tag技术对元素进行修改</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#使用lazy-tag技术对区间进行查询"><span class="nav-number">10.</span> <span class="nav-text">使用lazy-tag技术对区间进行查询</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#将一个区间整体置为一个数"><span class="nav-number">11.</span> <span class="nav-text">将一个区间整体置为一个数</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#求一个节点表示区间上所有元素的和"><span class="nav-number">12.</span> <span class="nav-text">求一个节点表示区间上所有元素的和</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#修改一个节点的值"><span class="nav-number">13.</span> <span class="nav-text">修改一个节点的值</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#修改整个区间的值"><span class="nav-number">14.</span> <span class="nav-text">修改整个区间的值</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#查询区间的和"><span class="nav-number">15.</span> <span class="nav-text">查询区间的和</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#总结"><span class="nav-number">16.</span> <span class="nav-text">总结</span></a></li></ol></div>
            
          </div>
          <div class="post-toc-indicator-bottom post-toc-indicator"></div>
        </section>
      

    </div>
  </aside>


    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner"> <!--
<div class="copyright" >
  
  &copy; &nbsp; 
  <span itemprop="copyrightYear">2015</span>
  <span class="with-love">
    <i class="icon-next-heart"></i>
  </span>
  -->
  <section class="poweredby">Build by laphets  -  Just A OIer  
  <section class="poweredby">Copyright © 2015 <a target="_blank" href="http://laphets.com/">laphets</a> . All Rights Reserved.
 <!-- <span class="author" itemprop="copyrightHolder">laphets</span> -->
<!--  
</div>
<div class="powered-by">
  由 <a class="theme-link" href="http://hexo.io">Hexo</a> 强力驱动
</div>

<div class="theme-info">
  主题 -
  <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
    NexT.Mist
  </a>
</div>
-->

 </div>
    </footer>

    <div class="back-to-top"></div>
  </div>

  <script type="text/javascript" src="/vendors/jquery/index.js?v=2.1.3"></script>

  
  
  
    

  
    
  

  <script type="text/javascript">
    var duoshuoQuery = {short_name:"laphets1"};
    (function() {
      var ds = document.createElement('script');
      ds.type = 'text/javascript';ds.async = true;
      ds.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//static.duoshuo.com/embed.js';
      ds.charset = 'UTF-8';
      (document.getElementsByTagName('head')[0]
      || document.getElementsByTagName('body')[0]).appendChild(ds);
    })();
  </script>
    
     

    
  
  
  <script type="text/javascript" src="/vendors/fancybox/source/jquery.fancybox.pack.js"></script>
  <script type="text/javascript" src="/js/fancy-box.js?v=0.4.5.1"></script>


  <script type="text/javascript" src="/js/helpers.js?v=0.4.5.1"></script>
  

  <script type="text/javascript" src="/vendors/velocity/velocity.min.js"></script>
  <script type="text/javascript" src="/vendors/velocity/velocity.ui.min.js"></script>

  <script type="text/javascript" src="/js/motion_global.js?v=0.4.5.1" id="motion.global"></script>




  <script type="text/javascript" src="/js/nav-toggle.js?v=0.4.5.1"></script>
  <script type="text/javascript" src="/vendors/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  
<script type="text/javascript" src="/js/bootstrap.scrollspy.js?v=0.4.5.1" id="bootstrap.scrollspy.custom"></script>


<script type="text/javascript" id="sidebar.toc.highlight">
  $(document).ready(function () {
    var tocSelector = '.post-toc';
    var $tocSelector = $(tocSelector);
    var activeCurrentSelector = '.active-current';

    $tocSelector
      .on('activate.bs.scrollspy', function () {
        var $currentActiveElement = $(tocSelector + ' .active').last();

        removeCurrentActiveClass();
        $currentActiveElement.addClass('active-current');

        $tocSelector[0].scrollTop = $currentActiveElement.position().top;
      })
      .on('clear.bs.scrollspy', function () {
        removeCurrentActiveClass();
      });

    function removeCurrentActiveClass () {
      $(tocSelector + ' ' + activeCurrentSelector)
        .removeClass(activeCurrentSelector.substring(1));
    }

    function processTOC () {
      getTOCMaxHeight();
      toggleTOCOverflowIndicators();
    }

    function getTOCMaxHeight () {
      var height = $('.sidebar').height() -
                   $tocSelector.position().top -
                   $('.post-toc-indicator-bottom').height();

      $tocSelector.css('height', height);

      return height;
    }

    function toggleTOCOverflowIndicators () {
      tocOverflowIndicator(
        '.post-toc-indicator-top',
        $tocSelector.scrollTop() > 0 ? 'show' : 'hide'
      );

      tocOverflowIndicator(
        '.post-toc-indicator-bottom',
        $tocSelector.scrollTop() >= $tocSelector.find('ol').height() - $tocSelector.height() ? 'hide' : 'show'
      )
    }

    $(document).on('sidebar.motion.complete', function () {
      processTOC();
    });

    $('body').scrollspy({ target: tocSelector });
    $(window).on('resize', function () {
      if ( $('.sidebar').hasClass('sidebar-active') ) {
        processTOC();
      }
    });

    onScroll($tocSelector);

    function onScroll (element) {
      element.on('mousewheel DOMMouseScroll', function (event) {
          var oe = event.originalEvent;
          var delta = oe.wheelDelta || -oe.detail;

          this.scrollTop += ( delta < 0 ? 1 : -1 ) * 30;
          event.preventDefault();

          toggleTOCOverflowIndicators();
      });
    }

    function tocOverflowIndicator (indicator, action) {
      var $indicator = $(indicator);
      var opacity = action === 'show' ? 0.4 : 0;
      $indicator.velocity ?
        $indicator.velocity('stop').velocity({
          opacity: opacity
        }, { duration: 100 }) :
        $indicator.stop().animate({
          opacity: opacity
        }, 100);
    }

  });
</script>

<script type="text/javascript" id="sidebar.nav">
  $(document).ready(function () {
    var html = $('html');
    var TAB_ANIMATE_DURATION = 200;
    var hasVelocity = $.isFunction(html.velocity);

    $('.sidebar-nav li').on('click', function () {
      var item = $(this);
      var activeTabClassName = 'sidebar-nav-active';
      var activePanelClassName = 'sidebar-panel-active';
      if (item.hasClass(activeTabClassName)) {
        return;
      }

      var currentTarget = $('.' + activePanelClassName);
      var target = $('.' + item.data('target'));

      hasVelocity ?
        currentTarget.velocity('transition.slideUpOut', TAB_ANIMATE_DURATION, function () {
          target
            .velocity('stop')
            .velocity('transition.slideDownIn', TAB_ANIMATE_DURATION)
            .addClass(activePanelClassName);
        }) :
        currentTarget.animate({ opacity: 0 }, TAB_ANIMATE_DURATION, function () {
          currentTarget.hide();
          target
            .stop()
            .css({'opacity': 0, 'display': 'block'})
            .animate({ opacity: 1 }, TAB_ANIMATE_DURATION, function () {
              currentTarget.removeClass(activePanelClassName);
              target.addClass(activePanelClassName);
            });
        });

      item.siblings().removeClass(activeTabClassName);
      item.addClass(activeTabClassName);
    });

    $('.post-toc a').on('click', function (e) {
      e.preventDefault();
      var targetSelector = escapeSelector(this.getAttribute('href'));
      var offset = $(targetSelector).offset().top;
      hasVelocity ?
        html.velocity('stop').velocity('scroll', {
          offset: offset  + 'px',
          mobileHA: false
        }) :
        $('html, body').stop().animate({
          scrollTop: offset
        }, 500);
    });

    // Expand sidebar on post detail page by default, when post has a toc.
    var $tocContent = $('.post-toc-content');
    if (isDesktop() && CONFIG.sidebar === 'post') {
      if ($tocContent.length > 0 && $tocContent.html().trim().length > 0) {
        displaySidebar();
      }
    }
  });
</script>



  <script type="text/javascript">
    $(document).ready(function () {
      if (CONFIG.sidebar === 'always') {
        displaySidebar();
      }
      if (isMobile()) {
        FastClick.attach(document.body);
      }
    });
  </script>

  
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    tex2jax: {
      inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
      processEscapes: true,
      skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    }
  });
</script>

<script type="text/x-mathjax-config">
  MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for (i=0; i < all.length; i += 1) {
      all[i].SourceElement().parentNode.className += ' has-jax';
    }
  });
</script>

<script type="text/javascript" src="http://cdn.bootcss.com/mathjax/2.5.3/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>


  
  

  
  <script type="text/javascript" src="/js/lazyload.js"></script>
  <script type="text/javascript">
    $(function () {
      $("#posts").find('img').lazyload({
        placeholder: "/images/loading.gif",
        effect: "fadeIn"
      });
    });
  </script>
<!-- mathjax config similar to math.stackexchange -->

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    tex2jax: {
      inlineMath: [ ['$','$'], ["\\(","\\)"] ],
      processEscapes: true
    }
  });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
    });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>

<script type="text/javascript" src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
</body>
</html>
